class Solution {
public:
    int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    class greater{
     public:
        bool operator()(const pair<int,int>& a,const pair<int,int>& b){
            return a.second > b.second;
        }
    };
    
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dist(m*n,INT_MAX);
        vector<int> vis(m*n);
        
        dist[0] = 0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater> que;
        que.push({0,0});
        
        while(!que.empty()){
            auto kv = que.top();
            que.pop();
            
            int u = kv.first;
            int w = kv.second;
        //    if(vis[u]) continue;
         //   vis[u] = 1;
            
            int x = u / n;
            int y = u % n;
            for(int k = 0;k < 4;k++){
                int nx = x + dirs[k][0];
                int ny = y + dirs[k][1];
                
                int v = nx * n + ny;
                int ndist = w + (grid[x][y] != k+1);
                
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && ndist < dist[v]){
                    
                    dist[v] = ndist;
                    que.push({v,dist[v]});
                }
            }
        }
        return dist[m*n-1];
    }
};
